package com.learn.learndemo;

public class SortUtilsCopy {

    /**
     * 冒泡排序
     * 时间复杂度O(n*n)
     * @param array
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * 每趟找最小，找到之后再交换
     * 时间复杂度O(n*n)
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[min]) {
                    min = j;
                }
            }

            if(min != i) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }

    /**
     * 插入算法
     * 在前面已经排好序的数组中，
     * 找到当前temp数据的位置，
     * 大于它的数据依次往后移动一位
     * 时间复杂度O(n*n)
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                if(array[j] > temp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }

    /**
     * 希尔算法
     * 将数组进行折半分组，之后进行比较
     * 折半区间越来越小，直到区间为1，达到相邻元素比较
     * 插入算法的扩充，每次间隔调换之后，需要向左按照gap间距向前比较
     * 时间复杂度O(nlogn)
     */
    public static void shellSort(int[] array){
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if(array[j] > array[j + gap]) {
                        int temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
        }
    }

    /**
     * 快速排序
     * 用第一个元素设定一个基准，
     * 从左找比基准大的数，从右找比基准小的数，之后进行交换，循环执行，在进行找的过程最终都执行同一个index
     * 将基准和index位置的值进行交换
     * 这个时候就得到两个数组，一个是大于基准，一个是小于基准
     * 再次对这两个数组使用递归使用快速查找，得到最终结果，
     * @param array
     * @param first
     * @param last
     */
    public static void quickSort(int[] array, int first, int last){
        if(first >= last) {
            return;
        }
        int key = array[first];
        int left = first;
        int right = last;
        while (left < right) {
            /**
             * 从右往左，找小于key
             */
            while (array[right] >= key && left < right) {
                right--;
            }

            /**
             * 从左向右，找大于key
             */
            while (array[left] <= key && left < right) {
                left++;
            }


            if(left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
        array[first] = array[left];
        array[left] = key;
        quickSort(array, first, left - 1);
        quickSort(array, left + 1, last);
    }
}
